import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 7, 7, 7, 7};
//      manyNumSort(arr);
//        manyNumRecursion(arr);
//        int num = manyNumRecursion(arr);
//        System.out.println(num);
        int manyNum = manyNumVote(arr);
        System.out.println(manyNum);
    }

    public static int manyNumVote(int[] arr) {
        int count = 0;
        Integer candidate = null;
        for(int i : arr){
            if(count == 0){
                candidate = i;
            }
            if(i != candidate){
                count--;
            }else{
                count++;
            }
        }
        return candidate;
    }


    //分治法
    public static int manyNumRecursion(int[] arr) {
        return manyNumRecursionInternal(arr,0,arr.length - 1);
    }

    public static int manyNumRecursionInternal(int[] arr, int left, int right) {
        if(left == right){
            return arr[left];
        }
        int mid = (left + right)/2;
        int leftNum = manyNumRecursionInternal(arr,left,mid);
        int rightNum = manyNumRecursionInternal(arr,mid+1,right);
        if(leftNum == rightNum){
            return leftNum;
        }
        int leftCount = arrCount(arr,leftNum);
        int rightCount = arrCount(arr,rightNum);
        return leftCount > rightCount ? leftNum :rightNum;
    }
    public static int arrCount(int[] arr,int value){
        int count = 0;
        for(int i : arr){
            if(i == value){
                count++;
            }
        }
        return count;
    }

    //排序法
    public static void manyNumSort(int[] arr) {
        Arrays.sort(arr);
        System.out.println(arr[arr.length / 2]);
    }
}
